package com.wxg.algorithm.chapter03.comparable;

import com.wxg.algorithm.chapter02.util.SortTestHelper;
import com.wxg.algorithm.common.ISort;

/**
 * MergeSortBU : BU(Bottom Up)自底向上
 *
 *
 */
public class MergeSortBU<T extends Comparable> implements ISort<T> {

    private MergeSortV2 ms;

    public MergeSortBU(){
        ms = new MergeSortV2();
    }

    @Override
    public void sort(T[] arr) {
        int n = arr.length;
        for( int sz = 1; sz <= n; sz += sz){
            for(int i = 0; i + sz < n; i += sz + sz){
                // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
                ms.merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n-1));

            }
        }
    }

    public static void main(String[] args) {
        MergeSortBU<Integer> ms = new MergeSortBU<>();
        int n = 10;
        Integer[] intArr = SortTestHelper.generateRandomArray(n, 0, 1000);
        SortTestHelper.printArray(intArr);

        ms.sort(intArr);

        SortTestHelper.printArray(intArr);
    }
}
